
// Definition for a Node.
function Node(val,prev,next,child) {
   this.val = val;
   this.prev = prev;
   this.next = next;
   this.child = child;
};

function createListWithArray(arr) {
  let head = new Node(arr[0], null, null, null),
      temp = head,
      nodeArr = [[head]],
      row = 0,
      end = true;
  for(let i = 1; i < arr.length; i++) {
    if(arr[i] == null) {
      if(end) {
        index++;
        temp = nodeArr[row][index];
      } else {
        end = true;
        continue;
      }
    } else {
      let node = new Node(arr[i], temp, null, null);
      temp.next = node;
      temp = node;
      nodeArr[row].push(node);
      end = false;
    }
  }


  return head;
}

function showList(head) {

}

/**
 * @param {Node} head
 * @return {Node}
 */
var flatten = function(head) {
  if(!head) return head;
  let stack = [head];
  while(stack.length) {
    let temp = stack.pop();
    // 如果该节点有孩子
    if(temp.child != null) {
      // 先装下一个节点，再装孩子,栈的思想
      if(temp.next) stack.push(temp.next);
      temp.next = temp.child;
      temp.child.prev = temp;
      stack.push(temp.child);
      temp.child = null;
    } else {
      if(temp.next == null) {
        if(stack.length) {
          temp.next = stack[stack.length - 1];
          stack[stack.length - 1].prev = temp;
        }
      } else {
        stack.push(temp.next);
      }
    }
  }
  return head;
};
let head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12];
console.log(flatten(head));
head = [1,2,null,3];
console.log(flatten(head));
head = [];
console.log(flatten(head));
